00005			CHAPTER ONE
00100	outline
00200	
00300	problem domain
00400		textured scenes
00500			outdoor scenes at the perspective of a human
00600	range of possible applications
00700		earth resources, agricultural survey
00800		planetary exploration
00900		industrial robots
01000		automatic driver
01100		metallurgy, SEM
01200		understanding of human perception and vision in AI
01300		synthesis of texture in design
01400	
     

00100	We intend to deal in this thesis with techniques for computer understanding
00200	of scenes with texture.  We consider examples of outdoor scenes, although
00300	textured surfaces appear in almost every sort of scene, and we show some
00400	examples of isolated and artificial textures.  Studies in computer vision
00500	are motivated by a wide range of applications.  Those involving texture include
00600	agricultural survey and analysis of earth resources satellite pictures.
00700	Planetary exploration by remotely controlled vehicles will demand some
00800	autonomous vision because of long delay times.  The social benefits
00900	of computer-controlled cars have been described by McCarthy.
01000	Industrial robots will
01100	soon acquire vision.  Texture synthesis, for which we feel our techniques
01200	are applicable, is useful in computer aided design and computer aided
01300	art.  Interpretation of scanning electron microscope pictures for metallurgy
01400	may be of interest.  We are also interested in constructing model of human
01500	perception.  Finally, vision is one of the more interesting problem areas
01600	within artificial intelligence, and contributes to the advance in our
01700	understanding of intelligent systems.
01800	
01900	Without a complete review of the literature, we would like to broadly
02000	contrast the work we have done with that of other areas in computer vision.
02100	Several small groups have studied perception of polyhedra.  Their work
02200	has been concerned with three-dimensional objects with plane, uniform
02300	faces.  The limited success of these efforts has depended to a large
02400	extent upon large homogeneous areas and isolated edges.  A number of
02500	prediction-verification techniques have arisen, some of which are special
02600	to the simple cases considered there.  Others are more general and useful
02700	to our work.  Because of the complexity of textured scenes, we feel that
02800	such considerations for perceptual systems are even more important for our
02900	work.
03000	
03100	Some work has been done with image processing, which is intended for
03200	improving the ease of human interpretation of images of particular value.
03300	[Quam,others].  Other work has been directed toward crop identification
03400	and other statistical summaries of the earth surface.  These studies
03500	have also made limited progress and are mentioned in a survey below.
03600	However, there is much room for improvemnt of texture description,
03700	and those studies completely ignore
03800	scenes where the three-dimensional character is important.
03900	
04000	It should be clear what we are really after in an interpretation
04100	of a scene.  the goal is not only to get a map of colored and textured regions.
04200	We are not merely after identification of some image as a
04300	member of a class.  That is, we are not out to identify the letter A.
04400	Nor do we wish to identify some region of the image as some previously
04500	seen element,although this might help us to achieve our goal.
04600	We have in mind a system with a task, to navigate, for
04700	example, and execution of the task requires understanding of the structure
04800	of the space portrayed by the image.
     

00100	Outline of Thesis
00200	
00300		In Chapter 1, after the statement of our problem,
00400	 we present an extensive review of literature that we
00500	think is relevant to an analysis
00600	of visual texture.  The literature covered in this review comes from
00700	three different sources: psychology, neurophysiology and computer
00800	science.  By no means is this review exhaustive.  However, we
00900	hope to show the reader, through the psychological and
01000	neurophysiological review, which features in grouping are important,
01100	and thus justify the features that we use for texture
01200	description.  The computer science review includes pattern
01300	recognition, linguistic and analytic approaches. 
01700	
01800		In the second chapter,
01900	instead of presenting some formal
02000	definition of a texture, which we do not believe is possible in
02100	general, we describe two concrete scenes with textured and
02200	colored regions. With these examples, we describe our representation
02300	of texture and of a real scene.  
02400	The third chapter presents the implementation of procedures which
02500	give us texture descriptors.  We discuss operators in the spatial
02600	domain, that is edge and region operators.  We discuss some of the
02700	techniques possible and problems to be encountered in extending these
02800	techniques to textured scenes.  Then we discuss texture descriptors
02900	derived in the Fourier domain.  Directionality turns out to be one of the
03000	most useful features, easily detectable in the Fourier domain.  We
03100	find that the Fourier technique has many problems, and we analyze the
03200	advantages and limitations of these descriptors.
03300	We show how to compute the size of texture elements and their contrast;
03400	These analytic expressions are evaluated for several examples and appear
03500	quite useful.
03600	
03700	Chapter four describes a region growing algorithm applied to forming
03800	textured regions and colored regions.  We present a sheaf-theoretic
03900	point of view which provides precise specification of conditions for
04000	continuity of textured or colored structures.
04100	
04200	Chapter five is devoted to the problem of interpretation of outdoor
04300	scenes.  We begin with an example of our earlier work with a pattern
04400	recognition approach to the classification of texture samples.  Then
04500	we present an analysis of the use of texture gradient in determining
04600	the orientation of surfaces and relative depth.  A simple world model
04700	is presented for outdoor scenes.  A discussion is made of higher level
04800	procedures which make interpretation of two examples of outdoor scenes.
04900	This higher level program has not been implemented, but gives a good
05000	perspective to evaluate the modules developed, and is the target for
05100	which we aimed.
05200	
05300	
05400	Contributions of this Research
05500	
05600	1
05700	A sheaf-theoretic formalism for describing textured and colored regions.
05800	
05900	2.  Description of textures
06000	
06100	3.
06200		Implementation of descriptors in terms of Fourier descriptors.
06300		Analytic expression of spacing, size and contrast of texture
06400		elements, and their approximate location.
06500	
06600	4.	Forming of color regions.
06700	5. 	Forming of textured regions.
06800	6.	Spatial interpretation of regions in terms of texture gradient
06900	7	Description of a higher level procedure and world model for
07000		outdoor scenes.
     

00005			CHAPTER TWO
00100	In  this  chapter  we  discuss  qualitative  descriptions  of  visual
00200	textures  in  order  to  suggest  the corresponding implementation in
00300	procedures.  Our aim will not be detailed descriptions; in a  Borgese
00400	story,  a  project to make perfect maps lead to maps the full size of
00500	the countries mapped. Instead, we want to characterize textures in  a
00600	compact  symbolic  representation which suggests correspondences with
00700	our models, and simplifies human communication  and  debugging.    We
00800	feel  that  everyday  texture  descriptions are good models for these
00900	purposes.  At a low level, we want to work with those descriptions to
01000	propose  plausible  colored and textured regions.  At a higher level,
01100	our aim is a description in object space, not  an  image  space  map.
01200	Many interpretations and hypotheses should be in terms of objects and
01300	properties of the object space.  An example is the interpretation  of
01400	texture gradient in the image as distance gradient in space.  Another
01500	interpretation is that an image region which can be continued  around
01600	another region is behind that region.
01700	
01800	
01900	2.1 EXAMPLES OF OUTDOOR SCENES
02000	
02100	In the scene shown in figure 3, we find three elements: grass, water,
02200	and  rocks.   The  grass lies on an approximately level surface.  The
02300	rock is in front of the  water  and  behind  the  grass.  We  do  not
02400	describe  the  image  itself,  but its interpretations as objects. In
02500	describing this scene, we emphasize its  segmentation  into  elements
02600	which  are  objects  and  regions  in  object space.  This structural
02700	description  characterizes  the  relationships  among   objects   and
02800	regions.  For example, a tree stands above the ground and in front of
02900	the sky. The structure allows us to  talk  about  complex  scenes  in
03000	terms  of  simple  elements.   To  move about, we must know where the
03100	grass extends, where to walk around rocks, and where  the  water  is.
03200	The  relationships  of objects are essential; even if we were able to
03300	store and recognize whole  scenes,  we  would  need  a  mechanism  to
03400	discover  where  we  walk,  what  we  can  pick up , that is what the
03500	spatial relationships of objects are.
03600	
03700	Grass, rocks and water correspond roughly to  three  regions  in  the
03800	image.   But  these  simple  elements  are  not  directly the sort of
03900	regions which come from existing edge  or  region  finding  programs.
04000	The elements we see are high level abstractions which do not coincide
04100	with color or texture regions.   In the first approximation, color is
04200	the most relevant feature that distinguishes these regions.  However,
04300	a closer look at the picture suggests that the  color  boundaries  do
04400	not  correspond  exactly  to  the  regions we see. Consider the white
04500	waves near the rocks or the dark areas inside the grass region.   Our
04600	texture region growing also defines a set of regions.  Directionality
04700	is important in the grass region, yet that property  is  not  uniform
04800	over the region.  Thus the regions defined by our texture descriptors
04900	do not coincide with the  grass  region  we  see.   Yet  there  is  a
05000	continuity  over  the region in some of the properties of color, size
05100	and density of grass stalks.  The fact that we have similar stalks of
05200	grass  over  the  whole  field (sometimes with different direction or
05300	with different color) makes it possible to propose the  field  as  an
05400	element.  This complexity makes it impractical to attempt to identify
05500	local elements with local prototypes for grass, sky, or water, or
05600	to attempt to identify the low level regions from our programs.
05700	
05800	
05900	In a second example in figure 5, we have four elements: grass, trees,
06000	clouds,   and   sky.    Again,   color  separates  the  sky,  clouds,
06100	grass,trunks of trees, and in some areas,  separates  the  crowns  of
06200	trees.  Texture, on the other hand, separates the trees from grass.
06300	
06400	In the object space description, the sky and trees are distinct.   We
06500	could arbitrarily define image regions  as  disjoint.   Proximity  of
06600	regions of like color is one basis for proposing a connectivity among
06700	tree branches and  among  fragments  of  sky.   Those  connectivities
06800	reflect  the  object space descriptions of trees as connected and sky
06900	as connected.   The regions based  on  proximity  in  the  image  are
07000	unconnected  and  overlapping.   That description allows an inference
07100	(which may not always be valid) that the trees are in  front  of  the
07200	sky.   Arbitrarily defining disjoint regions rejects these hypotheses
07300	of object space connectivity and the conclusion of interposition from
07400	overlap.
07500	
07600	Although  the  trees  are  approximately  of the same height, and the
07700	grass stalks are also roughly of constant height, their apparent size
07800	in  the  image decreases toward the center rear of the picture.   The
07900	size of the grass stalks nearest us is the same as that of the  trees
08000	farthest from us.  Gibson [1950] has perception relies heavily on the
08100	interpretation of systematic variation of apparent  size  with  image
08200	position  (texture  gradient)  as  a  variation  of distance from the
08300	observer.   For most purposes, the relative depth of elements in  the
08400	world  is  sufficient.   Assuming  that  we  know the position of the
08500	observer, the gradient allows us to determine the  absolute  distance
08600	of  objects.   The  measurement  of  observer  or camera position and
08700	angles,  and  calibration  of  the  image  device  [Sobel(1970)]  are
08800	essential.
08900	
09000	2.2 Textured Regions and Textured Elements
09100	
09200	The  examples  from  the  previous  section demonstrated a structural
09300	description of images by segmentation into elements of object  space.
09400	We  further  structure  these  textured  regions  in terms of texture
09500	elements and their spatial relationships.  In table 1  we  show  some
09600	examples  of  texture elements and their relationships as they appear
09700	in object space and image space.
09800	
09900	Texture elements cannot be determined in isolation.  A single element
10000	may  be  unrelated  to the texture.  The relationships are frequently
10100	only approximate.   In a texture of pebbles, the size similarity  may
10200	be  important  even though the sizes vary significantly; still, there
10300	is a uniformity within a factor of 10 or so.  Similarities  of  other
10400	properties  such  as  contrast,  shape, and spatial distributions may
10500	also be only approximate.
10600	
10700	In  practical   implementations   we   can   describe   only   simple
10800	relationships:  linear,  periodic,  regular but aperiodic, contiuous,
10900	symmetric,  and  the  like.   Likewise,  shape  descriptors  must  be
11000	relatively  simple.   One  may  question  the effectiveness of simple
11100	relationships and their descriptors; it is reasonable to think that a
11200	more  complex description of texture elements and their relationships
11300	is necessary for adequate description of textures. The  psychological
11400	experiments cited in chapter 1 indicate that human differentiation of
11500	textures depends heavily on a few simple descriptors such as contrast
11600	and  directionality,  and  ignores  even  curvature in making texture
11700	groupings.   Although we cannot estimate the computational complexity
11800	of  descriptors,  we have an intuitive feeling that in terms of time,
11900	or in terms of complexity of wiring for parallel systems, that simple
12000	descriptors such as directionality are clearly preferred.
12100	
12200	
12300	2.3 Textured Regions and Their Organization
12400	
12500	In the previous section we discussed images in a part/whole
12600	structure: scene-regions-elements.  The regions and elements were primarily
12700	in object space.  A texture may have a few layers of heirarchical structure;
12800	In figure   , the surfaces of the bricks have a rough texture.  The regions
12900	formed by the bricks are elements of the brick wall texture.  The textured
13000	region thus can be a texture element in a textured super-region, or the
13100	texture element may have micro-texture.
13200	
13300	Region and edge finders have some success with large homogeneous regions.
13400	Grouping of texture elements can be viewed as a generalization of homogeneity
13500	the regions of a common property correspond to the regions of homogeneity
13600	from a region growing operation.  The related operation of finding discontinuity
13700	in texture properties is analogous to edge-finding between homogeneous regions.
13800	Rosenfeld [] has discussed the problem of finding texture boundaries
13900	as that of finding gradients in the average values of statistical measures
14000	(which are assumed to be any suitable operator).  While this is suggestive,
14100	it unnecessarily emphasizes statistical measures
14200	as opposed to structured descriptions which would be more suitable for
14300	patterned textures.
14400	
14500	
14600		Let us approach the question of the organization of textured
14700	regions.  In the simplest case, the picture to be described is partitioned
14800	into a disjoint covering of textured regions.  A typical example of this
14900	situation is shown in figure    .
15000	
15100	A somewhat more complex system of regions can be described by a tree
15200	structure.  It may be used to represent the topological organization of
15300	the brightness contours (Krakauer (1970)).
15400	The structure of 
     

00005			CHAPTER FOUR
00100	In  the  previous  chapter,  we  discussed  procedures  for   texture
00200	descriptors. This chapter describes the determination of textured and
00300	colored  regions   and   introduces   a   mathematical   description,
00400	topological  sheafs,  to  formalize  the region-forming process.  The
00500	texture  descriptors  are  used  to   form   regions   with   similar
00600	descriptors.  The region-growing is low-level in that it does not use
00700	the context of a world model.  It is intended as a  tool  for  higher
00800	level routines which do not exist yet.  The proposed regions function
00900	as initial guesses about important areas  of  the  image.  Thus,  the
01000	routines  favor  large  regions  at the expense of smaller regions, a
01100	sort of "law of the fishes", the big  ones  eat  the  smaller.  Since
01200	there are few useful texture descriptors and organization procedures,
01300	this attention to low level modules was a  necessary  focus  for  our
01400	research.
01500	
01600	The  informal  distinction between low-level and high-level processes
01700	refers to the context which the process takes into account.  Roughly,
01800	we  mean  low-level when the context is local and based on the image,
01900	and by high-level  we  mean  an  object  space  interpretation  which
02000	depends  on several levels of abstraction and relations (global).  We
02100	would like a larger armament of  texture  descriptors  and  low-level
02200	organization  mechanisms.  However, it is important to have a balance
02300	between the low-level and higher-level systems,  and  to  design  for
02400	their communication.
02500	
02600	
02700	We emphasize that we use  a  technique  where  we  start  from  large
02800	windows  and take smaller windows at boundaries.  This approach has a
02900	limitation of missing  substructure.   The  microscopic  approach  of
03000	starting  from  small  windows  and  trying  to piece together global
03100	structure has a  complementary  weakness  of  missing  global  order.
03200	Overall,  we  think  this points up the need for a range of sizes for
03300	local organization.  For texture,  we  prefer  our  approach  to  the
03400	microscopic one.
     

00005			CHAPTER FIVE
00100	In chapter 2 we looked closely  at  elements  of  an  outdoor  scene,
00200	involving grass, sky, clouds, water, and trees.   One of our purposes
00300	was to introduce the  sort  of  texture  descriptors  which  we  have
00400	implemented.   The other was to lead the way into a discussion of our
00500	world model.  We saw a great range of variation for sizes, colors and
00600	other  properties of texture elements in these outdoor scenes.  Grass
00700	ranges in color through greens, browns,  and  yellows.   Trees  range
00800	from  a  few  feet  to a few hundred feet in height.  Because of this
00900	variation and the variation of apparent size of objects at  different
01000	distances   from   the   observer,   it  appears  that  no  immediate
01100	identification of image  textures  with  elements  of  the  world  is
01200	reliable.   In  some  cases,  the  understandings  depend  on perhaps
01300	unconscious reasoning: the spray on rocks  is  not  very  similar  in
01400	appearance   to   the   ocean   around   it.    In  many  cases,  the
01500	identifications are simply resolved by considering relations  between
01600	image  regions;  motion  obscuration  identifies  trees  in  front of
01700	clouds, shadows identify trees as standing above ground,  obscuration
01800	implies  a  background.  Relative depth determines that the ground is
01900	roughly level and that trees stand above the ground.
02000	
02100	It is reasonable to question whether a model which must allow as much
02200	flexibility  as  to  allow  the  range  of sizes for objects, and the
02300	variation in relations, is of any use at all.  There are several ways
02400	in  which  it  is. The first is that certain relations are reasonably
02500	stable.  The sky is bright against the horizon.  The  proportions  of
02600	grass,  and  trees  are roughly independent of size.  Certain regular
02700	shapes are usually man-made. The second is that much of the variation
02800	is  connected  with  various  subsidiary conditions.  If trees appear
02900	different  colors,  they  are  different  species,  and  have   other
03000	identifiable  properties.   If  the  grass is yellow, then it must be
03100	dry.  An apparent size gradient probably means a distance gradient.
03200	
03300	However, the usual mode of perception is continuous  perception.   In
03400	scene  analysis,  we  often think of showing a single picture with no
03500	context and expect the observer to understand it.  Indeed, humans can
03600	do  just  that  usually.   But  the  bulk  of  perceptual activity is
03700	involved in moving in a world in  which  changes  happen  slowly  and
03800	locally.   Most  of  the world is nearly unchanged from one moment to
03900	the next.  Most of the recent perceptual understandings are useful at
04000	any  instant; the system knows a great deal about the environment and
04100	makes incremental changes to its model.  The making of the changes to
04200	the  model is aided by the detail of the knowledge already available.
04300	
04400	That  does  not  mean  that we can do without the ability to actually
04500	build up the model, either from the picture shown out of context,  or
04600	guided  by  an already detailed model.  But it does mean that a large
04700	part of perceptual activity is guided by detailed models.
04800	
04900	Another aspect of the world model is that it contains the information
05000	about the observer's point of view.  The observer's motion provides a
05100	depth sense equivalent to stereo, but much more  useful  for  distant
05200	objects.  Distance  estimates  using  motion  parallax  depend on the
05300	observer's estimate of  his  motion.   Stereo  distance  measurements
05400	depend upon a model for the convergence position of the two eyes, the
05500	eye separation, and correspondence of the coordinate systems  of  the
05600	two  eyes.  An equivalent observer model has been implemented at this
05700	laboratory in the work of Sobel [], Tenenbaum  [],  and  the  use  of
05800	observer's  motion  for  depth  perception  has  been  implemented by
05900	Nevatia [].
     

00005			CHAPTER SIX
00100	The model contains the ground plane which is approximately smooth and
00200	level.  That condition assumes that relative distances which are
00300	accurate for a plane are locally approximate for the ground plane.  
00400	The model also includes the abstract idea of object which is something
00500	distinct and localizable, and stands above the ground plane.
     

00100	We discuss briefly a suggested higher level program which
00200	we simulate.  We concentrate on the two scenes in figeures   and   .
00300	call them WATER and ROSES respectively.  There are three gross
00400	parts of this process of interpreting the structure of the scenes.
00500	These might be called
00600		organization of regions having continuous properties
00700		determination of spatial relations
00800		identification of elements in object space;
00900	they are not strictly heirarchical, since identification determines
01000	new spatial relations, and suggests other low level organizations.
01100	
01200	Some of the mechanisms for organization of continuous regions
01300	were previously discussed.  The
01400	regions based on continuity in color and some texture descriptors are
01500	natural starting places.  Proximity provides the basis for the suggestion
01600	of texture super-regions which are disconnected, but may be usefully
01700	considered as a unit.  In this operation, we group together nearby regions
01800	of like color or like textural properties.  The next mechanism is that of
01900	hypothesis-verification:  a particular color or texture region is a
02000	hypothesis of continuity.  If the region has some physical continuity,
02100	we should find that other properties are continuous over the region.
02200	If the boundaries are false, then there should be textural properties
02300	which continue across the boundary, from which we would assume a continuity
02400	which would be tested by looking for other continuity.  If the boundaries
02500	correspond to physical boundaries, we will usually be able to find a
02600	discontinuity in some textural property.
02700	
02800	We can infer a few spatial relations from the texture gradient, from
02900	guesses about interposition (which object is in front of which) and
03000	from the observer orientation and postition, combined with the ground
03100	plane hypothesis.  In a complete system, we could call on depth perception
03200	by stereo and motion parallax.  Our inferences would be a good guide
03300	to economical use of these modules.
03400	
03500	Identification, in our suggested system, proceeds both from the world
03600	model and from the data.  Some elements of the world model are better
03700	starting places than others.  We assume that the sky would be easily
03800	established in most cases.  Other image elements should be approached
03900	after finding the important structural elements in object space, ie
04000	sky, ground plane, and trees.  We are assuming that a full variety
04100	of properties and relations aid us in making initial and tentative
04200	identifications of sky,etc.
04300	
04400	In figure 1, which we call WATER, we have two major regions which
04500	correspond to grass, a region which corresponds to the rock, and two
04600	regions which correspond to the water.  In the  scene called ROSES,
04700	the sky appears as one large region and several small regions, there
04800	are three regions of the bush, and several small regions which correspond
04900	to roses.
05000	
05100	In the analysis of these two scenes based only on texture without guidance,
05200	the scene WATER is described partly adequately.  After the texture gradient
05300	suggests further continuities, the grassy regions merge, and there remain
05400	three main image elements which correspond to grass, rock, and water.  
05500	This texture organization is suitable for providing hypotheses of continuity
05600	for regions which are broken by color organizaion.  The similarity in color
05700	of the joined color regions confirms the texture continuity.  In ROSES,
05800	the sky is adequately described by texture, while the bush and flower
05900	regions are chaotic.  This reflects one of the inadequacies of the Fourier
06000	transform, the weakness with feature sizes approaching the window size.
06100	This is normally accomplished by subdividing regions with slow changes
06200	which correspond to probable region boundaries.  That was suppressed in
06300	this version of the program.
06400	The region-growing does not succeed in isolating
06500	the flowers by cutting up windows containing flowers to partition off smaller
06600	cells of adjoining areas of the bush.  This is the worst performance of
06700	the texture region finding process, but it is instructive.  On the whole,
06800	the unaugmented texture region analysis is unable to aid in proposing useful
06900	alternative hypotheses for organization.  However, texture boundaries for the sky
07000	coincide with color boundaries, and a slight relaxation of the criteria
07100	for continuity, verified by continuity in contrast among the color components,
07200	does provide a set of larger texture regions among the bush and flowers.
07300	Even in that worst case, the jumbled areas of color correspond to regions
07400	of moderate size under texture, so that there are no large regions of the
07500	picture which appear entirely chaotic under both aspects.
07600	The texture descriptors are useful for analyzing the color regions, and
07700	have more utility used in that directed mode.  The element size and contrast
07800	are meaningful when restricted to the bush; in the unaided texture analysis,
07900	these descriptors mix the flowers and bush.
08000	
08100	In evaluating our higher level procedures, it is usual that we re-evaluate
08200	the quality of  the lower level modules.  We find significant ways in which
08300	they could be improved, and in ways which would best be done at that level.
08400	In general, it is better to proceed to a fully developed system than to
08500	put disproportionate work at the low level.  We will later specify 
08600	what improvements we would make in the low level modules.
08700	
08800	Let us make the preliminary organization of the two scenes.  With ROSES,
08900	we begin with proximity of color regions.  The bush regions and the
09000	flower regions are alike in color; for example, in two areas of the bush,
09100	the color coordinates r/(r+g+b) and g/(r+g+b) are:
09200			sample 1   (.46,.43)
09300			sample 2   (.47,.40)
09400	thus we can conjecture these two super-regions.  Although we do not have
09500	access to the texture descriptors for the regions defined by color,
09600	our experience with the texture descriptors gives us good reason to believe
09700	that the estimates of contrast, size and element spacing are adequate to
09800	verify some common texture properties for the conjectured regions including
09900	roses and bush.  In the scene, the sky is a region under color and all texture
10000	descriptors.  The sky boundary in color is reinforced  by the existence of
10100	texture boundaries.  As we have indicated, textural properties are probably
10200	adequate to confirm continuity of the regions suggested by color for bushes
10300	and flowers, and to show discontinuities of frequency.  In WATER, the two
10400	regions corresponding to water are joined by proximity in color and continuity
10500	in texture.  The water boundary shows up strongly as a change in color and
10600	in texture, directional to homogeneous for the water-rock boundary, and
10700	different directionalities with distinctly different color at the water-grass
10800	boundary.  The grass is continuous in directionality, size, and color.
10900	
11000	We can now make correspondence with the world model.  Since the sky is
11100	often prominent in outdoor scenes, we attempt to find the sky.  We look
11200	at white and blue regions which are near or above the horizon.  In WATER,
11300	we might try the region which is really water.  The color is acceptable,
11400	but the directionality is very unlikely for sky, and the contrast and size
11500	of texture elements is also unlikely.  (This estimate is based on a few
11600	months of sporadic sky watching.  Of course there are directional clouds,
11700	"mackerel sky", but it seems quite infrequent.  Also, the clouds seem to
11800	have much lower frequency.)  The water region is below the horizon.  If
11900	there were a significant view, we could see a texture gradient and thus
12000	substantiate that the surface is flat.  Also, in continuous perception,
12100	we would find that the water motion is very different from cloud motion.
12200	Motion would also allow interpretation of the breakers around the rock
12300	as part of the water.  The region corresponding to grass is directional,
12400	low contrast, and has a texture gradient, implying that it is horizontal.
12500	The color is consistent with grass, which lies on the ground plane.  From
12600	the ground plane assumption, we can estimate the size of the elements of
12700	the grass:
12800			image size*angular resolution*distance
12900			= 2*(1/666/*300 cm =.9cm
13000	where we estimated the image size previously, the camera parameters are
13100	known, and the distance is obtained from a crude guess, but is known in
13200	principle from the observer position and orientation.  The size is also
13300	consistent with grass blades.  For the rock, neither color nor homogeneity
13400	tell us very much.  Since the rock is convex downward on its boundary
13500	with water, we assume that the rock is front of the horizontal water surface
13600	We assume thus that it is an object which sticks up from the surface, and
13700	calculate the vertical height and length along the ground.  From the image,
13800	the texture gradient tells us that the distance at  the rock is about 4 times
13900	that at the front of the picture.  Thus, the above expression gives:
14000			18*(1/666)*1200cm=36cm
14100	while the width of the rock is approximately 300cm.  These are only
14200	approximate values which depend on our guesses about the ground plane
14300	and texture gradient.  On the other hand, the conclusions depend most strongl
14400	on relative size conclusions.  Grass elements are small; rocks are oftne
14500	big compared to grass.
14600	We can make the comparison between the rock and grass near the base of the
14700	rock.
14800	In the image, the rock is big, and from all
14900	assumptions about objects in the image being further away as they recede
15000	in apparent position toward the horizon, the rock is much bigger than the
15100	elements of the grass.  These give some strength to the assumption.
15200	
15300	In ROSES, we begin by attempting to find the sky.  The only region of
15400	acceptable color is the sky itself.  The color is white, indicating clouds.
15500	The texture is homogeneous.  As a verification, we might find blue patches,
15600	find motion, and find that the distance of this region is very great.
15700	The region is far above the horizon, and is very bright.  From the concave
15800	downward boundary with the other regions, we assume that it is behind
15900	the green elements.  With the identification sky; we find that the green
16000	elements are in front of the sky, thus probably approximately vertical,
16100	and are frontal (they show no systematic texture gradient), also indicating
16200	that they are vertical.  The texture is blob-like; the blob size is interesting.
16300	If we can guess that these are leaves rather than leaf clusters or branches,
16400	then we can extimate the distance to the bush.  Finding the stems would
16500	aid in that.  Because the bush is probably vertical, it is not grass.
16600	If we include leaf elements, fruits and flowers in our descriptions of
16700	trees and bushes, then by guessing that the flowers are really associated
16800	with the bush which surrounds them, we can guess the scale of the leaves
16900	relative to the flowers, and thus establish that the texture elements are
17000	leaves and establish approximate distance.  Of course, at any level, we
17100	could establish relatively unique elements to correspond in two views,
17200	and determine distance by stereo or motion.
17300	
     

00100	outline
00200		representation of texture
00300			three dimensional
00400			texture elements
00500			texture regions
00600			heirarchy of textures
00700			representation of shape
00800			texture gradient
00900			world model
01000		representation of region-growing
01100			Sheaf formalism
01200		color regions
01300			color continuity
01400			proximity
01500		texture regions
01600			texture descriptors
01700				Fourier, technical difficulties not too important
01800					FFT is a Fourier series
01900						non-isotropic, diff with fan filter
02000						spurious amplitude(not sharp F(phi))
02100					fan filter is not designed to deal with digitization
02200				Fourier, useful descriptors
02300					some organization and repetition
02400					directionality,non-directionality
02500					contrast
02600					element size and spacing
02700				Fourier conceptual disadvantages
02800					color
02900					lack of edges and spatial information
03000						don't understand how to use phase
03100					mixing of shading and outline
03200					mixing of element shape with relations between
03300								elements
03400				Fourier, incremental improvements to descriptors
03500					interval analysis for directional
03600					Fourier color componenets
03700					edge operators for spatial location, perhaps
03800							on filtered images
03900			texture regions
04000				Fourier definition of regions (very important range of sizes of windows)
04100					classification
04200					continuity of frequency, etc. and descriptors
04300					change scale
04400						frequency 1
04500						bi-directional
04600					pass 2 
04700						relaxes criteria and classification
04800						extends large regions into small
04900				Region growing controlled by hand
05000					within a set of windows (controlled by color)
05100					separate parameters
05200	
05300				Fourier, incremental improvements to organization
05400					increase scale for large wavelengths
05500					decrease scale for large wavelengths
05600					multiple descriptions
05700					guided by color regions, etc.
05800		high level procedures
05900			hypothesis-verification of regions
06000				continuity
06100				discontinuity
06200			spatial relations
06300				texture gradient
06400				ground plane
06500				interposition
06600				complete system with depth modules
06700			correspondence with world model
06800				sky if any
06900					color
07000					above horizon
07100					contrast with horizon
07200					element size
07300					interposition
07400					motion
07500	
07600	
07700	
     

00100	We presented a representation of textured scenes which was not a two-
00200	dimensional   representation   of   the   projected   image,   but  a
00300	three-dimensional  representation  of  the   elements   and   spatial
00400	relations in object space. We feel that the representation of spatial
00500	relations such as grass is found on the ground plane and  the  nearly
00600	infinite  distance  of  the sky are characteristic of these elements,
00700	and help more than any other  properties  to  identify  them  and  to
00800	orient  the  observer. Our representation is effective, also, in that
00900	it is segmented into distinct elements,  which  are  described  by  a
01000	heirarchy  of  texture  regions.   and  textured elements.   Textured
01100	regions may be texture  elements  of  a  super  texture,  or  texture
01200	elements may be textured regions of a sub-texture.   This is not only
01300	a formal nicety, but a usual part  of  our  descriptions  of  outdoor
01400	scenes;  for  example,  in  trees, the leaves are texture elements of
01500	leaf clusters or branches, which are  texture  elements  of  a  tree,
01600	which is a texture element of tree clusters. The description of shape
01700	of texture elements depends heavily  on  a  linear  approximation  to
01800	shape,  and  describes directionality, width of textrue elements, and
01900	spacings.  We argue from psychological evidence that  these  are  the
02000	most important of descriptors, and further, that they are natural for
02100	computer implementation.   These  descriptors  are  most  useful  for
02200	directional textures. The representation is included in a world model
02300	for which an example was given, but which awaits implementation  with
02400	the high level procedures.
02500	
02600	A  simple  color region analysis was very useful in texture analysis.
02700	The  normalized  color  coordinates,  r/(r+g+b)  and  g/(r+g+b)  were
02800	compared  for  continuity,  and  regions were defined by neighbors of
02900	continuous color.  There are some potential problems in  an  analysis
03000	of  color  in  outdoor scenes, since many of the texture elements are
03100	very small.  Typically, the regions are leaves or blades of grass. As
03200	an  expedient  to  find larger regions, we have averaged over a small
03300	window, and compared colors of adjacent windows.  As  a  consequence,
03400	we sacrificed localization of edges.  The expedient is only partially
03500	successful however.  We notice that the averaging  works  best  among
03600	clusters  of  leaves where the color is uniform to begin with.  Where
03700	the leaves are isolated against the sky, the color contrast is large,
03800	and  continuity  of  the  averages  are  only  by  chance.  Thus, the
03900	averaging is not very successful.    A  better  mechanism  to  define
04000	larger  regions of color is perhaps to go to the computationally more
04100	difficult operation of finding like colors within windows, that is to
04200	implement  color  regions  based on proximity rather than continuity.
04300	The  obvious  value  of  defining  color  regions  which  ignore  the
04400	brightness  fluctuations  of  individual leaves should not lead us to
04500	ignore brightness edges and consider color edges. We also make use of
04600	the size of the brightness regions, the leaves in this case.
04700	
04800	A    sheaf-theoretic    description   formalizes   the   process   of
04900	region-growing and gives an exact account of the shift from local  to
05000	global  and  vice versa.  One must be cautious about interpreting the
05100	sheaf-theoretic notions in the context of color and texture  regions.
05200	Due  to  sampling,  we  have  a  finite scale of window sizes and the
05300	definition must include a least window  size,  the  size  of  texture
05400	elements.   No  such  discreteness  conditions  are embedded in sheaf
05500	theory.
05600	
05700	In the  implementation  of  texture  descriptors,  we  were  able  to
05800	translate  those  spatial  domain descriptors that we found important
05900	from Fourier transforms over windows of various sizes.    Directional
06000	and  non-directional  components  were  separable to a useful extent.
06100	These  reflected  shapes  of  texture  elements  and  their   spatial
06200	relations,  or  statistical  properties  of  irregular  textures.  We
06300	argued that the human description of an image makes  use  of  a  step
06400	function  approximation;  we  often  describe  in terms of regions of
06500	constant  intensity.    We  obtained  analytic  expressions  for  the
06600	contrast,   the   element   size   and  spacing,  and  some  location
06700	information; these were based on a spatial domain model of pulses  of
06800	equal  amplitude,  width  and spacing, on a uniform background level.
06900	The implementation of Fourier transform descriptors  had  some  minor
07000	implementation  difficulties  which are usually overlooked.  They are
07100	consequences of the fact that the Fast Fourier Transform is really  a
07200	Fourier  series and not a Fourier transform.  A Fourier transform has
07300	no preferred directions, while the Fourier series has preferred  axes
07400	along the x and y coordinate axes.  This introduces a non-isotropy in
07500	the fan filter.  We have used only a straightforward fan  filter  and
07600	have not attempted to compensate for the peculiarities of the Fourier
07700	series.  There are  also  spurious  broadening  of  peaks  which  are
07800	consequences  of the Fourier series.  Despite these difficulties, the
07900	spectra show useful directionality properties, and we have been  able
08000	to work with them.
08100	
08200	The  more serious problems with the Fourier transforms are conceptual
08300	difficulties which are true of any orthogonal expansion  and  of  the
08400	true Fourier transform. Interpretation is based on the power spectrum
08500	and phase information is ignored. These transforms are non-local, and
08600	give  very poor edge and position information.  To an extent, we have
08700	tried to get around this by an expedient of using local windows. This
08800	provides  a  crude  localization,  which  was  not  adequate for many
08900	purposes.  The usefulness of the transforms was very dependent on the
09000	scale  of  the  windows.    The descriptors were most useful when the
09100	window size was such as to exclude other regions and to include  some
09200	repetition  of texture elements within the window.  This meant that a
09300	range of window sizes was necessary, and that  we  could  not  always
09400	have  windows  small enough or large enough.  To a certain extent, we
09500	could  probably  get  positional  information   from   our   analytic
09600	expression using the phase of the transform.  However, that is useful
09700	only for uniformly spaced texture elements.  In  most  useful  cases,
09800	the spacing is quite irregular. The non-local nature of the transform
09900	is a severe disadvantage in using color information.    As  in  other
10000	cases,  we can make examples where the averaged quantities are useful
10100	in smearing out and bridging  local  boundaries.   This  has  limited
10200	utility.   There are a few simple cases for which the color contrasts
10300	can be extracted from the Fourier transforms of separate  intensities
10400	through  three  filters.  We have not yet incorporated these into our
10500	descriptors.
10600	
10700	There are some incremental improvements to be  made  to  our  Fourier
10800	descriptor  scheme.    One  of  these is to use interval analysis for
10900	determining widths and locations of  discontinuities  in  directional
11000	textures.    In some cases, overlapped windowing would be useful near
11100	boundaries.  Including Fourier color components was mentioned  above.
11200	We  should  include  edge  and  region operators (perhaps on filtered
11300	directional components) to find the extent of linear elements and  to
11400	find boundaries of quasi-homogeneous regions.
11500	
11600	Textured   regions   were  obtained  on  the  basis  of  the  texture
11700	descriptors. We found that a range of window sizes was necessary; our
11800	strategy was not adequate to use the window sizes as well as it might
11900	have.  The choice of window sizes would  be  better  left  to  higher
12000	level  choice among suggested regions.  The actual program which gave
12100	textured regions classified  the  texture  descriptors  according  to
12200	mono-directional,  bi-directional, blob-like, homogeneous, and noisy.
12300	Then adjacent regions were merged into continuous  regions  based  on
12400	continuity  of  the descriptors.  A change of scale was used if there
12500	was a strong frequency 1 component (that is, there  probably  was  an
12600	edge  in  the  window) or if there was a bi-directional texture which
12700	could arise from a boundary of two directional textures.    A  second
12800	region-growing  pass relaxes the criteria and ignores classifications
12900	to extend large regions by  including  acceptable  small  neighboring
13000	regions under relaxed criteria.
13100	
13200	A  guided  program  determined  textured regions based on information
13300	passed down from above.  This program was guided by the user, but the
13400	advice  could equally well have come from other programs.  The guided
13500	programs  determined  texture  regions  within  specified  areas  and
13600	according  to  specified  similarity criteria, for example, frequency
13700	and contrast. Continuity could be explored on the basis of  sseparate
13800	parameters.
13900	
14000	
14100	We see some incremental improvements to the region-growing  based  on
14200	Fourier  descriptors.   We  would add an alternate tactic for windows
14300	with long wavelengths; now we subdivide based on the  possibility  of
14400	an  edge  in  the window.  We would also increase window size to look
14500	for a repeated feature of a larger  size.   We  would  eliminate  the
14600	classification step now used.  There is some argument in favor of the
14700	classification.   There are actually many natural objects which  fall
14800	into  one  or another of these classes. But the classification in the
14900	early  stages  introduces  artificial  boundaries  and  ignores   the
15000	multiple  descriptors  which are available.  Only later does it relax
15100	these classes.   A further and more significant addition would be  an
15200	implementation of proximity of like descriptors on nearby windows for
15300	texture super-regions.
15400	
15500	We presented an outline for  a  higher  level  procedure  to  make  a
15600	correspondence between the image elements and the world model.   This
15700	outline was not implemented  but  simulated  in  two  examples.   The
15800	striking  conclusions from the simulation were that interpretation of
15900	the three-dimensional structure of the scene was  necessary  to  make
16000	the   identification.     This   contrasts  with  the  work  done  in
16100	interpretation  of  aerial  photographs,  for  which  the  world   is
16200	effectively  on  a locally flat surface, and depth considerations are
16300	unimportant. A perceptual system begins to have interesting structure
16400	when  it  can work with more than a single property.  Our model deals
16500	with multiple properties by a  hypothesis-verification  paradigm  for
16600	proposing  boundaries  and regions.  Continuity in a physical surface
16700	can be hypothesized on the basis of one of  the  properties.   Often,
16800	the  region  description  from some one property will be particularly
16900	simple and useful.   It is not clear  that  we  can  always  pick  in
17000	advance  which  property  it  is;  with  sufficient  context we could
17100	usually make a good choice.  But we can try several different choices
17200	as  hypotheses  of  meaningful  surfaces, and test that continuity in
17300	that  property  corresponds  to  continuity  in   other   properties;
17400	discontinuity  in  physical surfaces often reflect discontinuities in
17500	several properties. In these examples, color regions were joined into
17600	color  super-regions  of like color.  Textural properties of dominant
17700	frequency and contrast showed continuity of these properties over the
17800	color  super-region.   At  this  point, the lower-level modules could
17900	function in a guided mode to expand the region corresponding to these
18000	typical  descriptors and include nearby areas of the image which were
18100	not well- described in the earlier analysis with little context.
18200	
18300	The regions which come forth do not make a neat image.  They  overlap
18400	and  do not cover the whole image.  Still, we are aiming to interpret
18500	those parts of it that  are  simple  to  understand.   Inferences  of
18600	spatial   relations  are  important  here.    Texture  gradient  gave
18700	estimates of surface orientation.  The ground plane assumption gave a
18800	local  coordinate  system  when  combined  with  the  assumption that
18900	objects stand out from the ground. Thses relations depended primarily
19000	on  relative  distance  and  relative  size  estimates which were not
19100	greatly sensitive to the assumptions.  In some cases it was  possible
19200	to  guess  which  object  was  in front of another, either because of
19300	concavity, or from identification of the sky or water.
19400	
19500	
19600	In  identifying  elements  and  structure  of  the  world  model, our
19700	simulation attempted first to establish the  sky.   Based  on  color,
19800	brightness,  contrast  with  the horizon, and its position (above the
19900	horizon estimated by gravity), this is assumed a  simple  match.   We
20000	can  also  then  determine the sky line and guess which objects stand
20100	out from the ground  plane.    Sizes  of  texture  elements  were  of
20200	considerable  use; knowledge of size is much more useful here than in
20300	the blocks world where context is limited.  The knowledge of the size
20400	of  grass blades is more useful than the knowledge of the size of one
20500	particular block.
20600	
20700	We have mentioned some  incremental  improvements  to  texture  local
20800	description  and  to forming texture regions.  The primary weaknesses
20900	at this level are the crude localization and limited use of proximity
21000	in establishing
21100	
21200	super  regions.  Improvement of the color region-finder is of primary
21300	importance.     Since  much  of  the  interpretation  depended   upon
21400	inferences separate from strictly textural properties of areas of the
21500	image, we feel that the most significant next stage is to embed these
21600	elements  in  a complete visual system.  This would involve more than
21700	just implementation of  the  simulated  higher  level  program.   The
21800	typical  system would navigate in an outdoor or planetary exploration
21900	environment.   The navigation goals make explicit which problems  the
22000	system  needs  to  solve  at  any  time.    The  situation  is one of
22100	continuous perception which allows the model built up at one  instant
22200	to be used in subsequent problem-solving.  Continuous perception also
22300	allows us to tell which objects  are  moving,  which  is  of  use  in
22400	outdoor  scenes.   The  complete  system would have stereo and motion
22500	parallax for depth at  small  and  great  distances.   To  a  certain
22600	extent, the system would avoid finding solutions which could be found
22700	purely from single projections, but such a  system  appears  feasible
22800	within  the  current  state  of computer vision, while a system which
22900	ignores so much information does not appear to be achievable soon.